//
// Created by tianq on 25-1-6.
//

/**
input:
first line n: line count
following n lines: p1,p2,w
p1,p2: ends of the line, points are int
w: weight

output:
lines in the tree & minimal power

 */
#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>

using namespace std;

std::ostream &operator<<(std::ostream &os, std::unordered_set<int> const &s) {
    for (os << '[' << s.size() << "] { "; int i: s)
        os << i << ' ';
    return os << "}";
}

struct Dom {
    unordered_set<int> points = {};
    int weight = 0;

    Dom(const unordered_set<int> &points, const int weight) : points(points), weight(weight) {
    }

    bool operator<(const Dom &other) const {
        return weight < other.weight;
    }

    Dom operator+=(const Dom &other) {
        points.insert(other.points.begin(), other.points.end());
        weight += other.weight;
        return *this;
    }
};

int main() {
    vector<Dom> edges, domains, mst;

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int p1, p2, w;
        cin >> p1 >> p2 >> w;
        if (p1 == p2) w=0; // isolated point, we are leaving it here to check if orphans exists
        edges.emplace_back(unordered_set{p1, p2}, w);
    }
    // edges.emplace_back(unordered_set{1, 2}, 10);
    // edges.emplace_back(unordered_set{2, 3}, 30);
    // edges.emplace_back(unordered_set{1, 3}, 20);

    // start with the shortest vector
    sort(edges.begin(), edges.end());

    for (const Dom &e: edges) {
        cout << endl;
        cout << "parsing edge: " << e.points << ", weight: " << e.weight << endl;

        Dom new_dom = e; // adding the edge forms a new connected domain
        vector<Dom> orphans; // after adding the dom, some domains stay orphaned
        bool is_loop = false; // skip the edge if a loop is found

        // try to merge dom to edge to get a single connected domain
        for (const Dom &d: domains) {
            cout << "domain: " << d.points << ", weight: " << d.weight << " - ";

            // check intersection
            bool has_intersection = false;
            bool all_intersection = true;
            for (const int &point: e.points) {
                const bool found = d.points.contains(point);
                has_intersection = has_intersection || found;
                all_intersection = all_intersection && found;
            }

            // adding the edge forms a loop, we must stop now, this edge shouldn't be added
            if (all_intersection) {
                cout << "loop found! skipping" << endl;
                is_loop = true;
                break;
            }

            // domain contains a point from the vector, merge it to newDom
            if (has_intersection) {
                cout << "intersect found, merging" << endl;
                new_dom += d;
            }

            // no connection found, leave it orphaned
            else {
                cout << "no intersect, leaving orphaned" << endl;
                orphans.emplace_back(d);
            }
        }

        if (is_loop) continue; // loop found, skip this vector
        if (new_dom.points.size()==n){
            cout << "finished" << endl;
            break; // finished
        }

        mst.emplace_back(e);
        orphans.emplace_back(new_dom);
        domains = orphans;

        cout << "new_dom: " << new_dom.points << ", weight: " << new_dom.weight << endl;
    }

    cout << endl;
    if (domains.size() != 1) {
        // cout << "orz";
        cout << "domains must contain exactly one element, the graph is not connected" << endl;
        cout << "islands: " << domains.size() << endl;
        for (const Dom &d: domains)
            cout << "domain: " << d.points << ", weight: " << d.weight << endl;
        return 1;
    }

    cout << domains[0].weight << endl;
    for (const Dom &d: mst) {
        cout << "(";
        for (const int &point: d.points)
            cout << point << ", ";
        cout << "\b\b)";
    }
}
